#include <cassert>

#include "FixedSizeAllocator.h"



namespace MemMgr
{

FixedSizeAllocator::FixedSizeAllocator(void) :
	mChunks(),
	mBlockSize(0),
	mNumBlocksPerChunk(0),
	mLastAllocationChunk(nullptr),
	mLastDeallocationChunk(nullptr),
	mOnlyOneEmptyChunk(nullptr)
{
}



FixedSizeAllocator::~FixedSizeAllocator(void)
{
	ChunksIter it = mChunks.begin();
	for (; it != mChunks.end(); ++it)
	{
		//assert(it->HasAvailableBlocks(mNumBlocksPerChunk) && "All blocks must be deallocated: prevent memory leaks!");
		it->Release();
	}
}



FixedSizeAllocator::FixedSizeAllocator(const FixedSizeAllocator& iOther) :
	mChunks(),
	mBlockSize(iOther.mBlockSize),
	mNumBlocksPerChunk(iOther.mNumBlocksPerChunk),
	mLastAllocationChunk(nullptr),
	mLastDeallocationChunk(nullptr),
	mOnlyOneEmptyChunk(nullptr)
{
	assert(iOther.mChunks.empty() && "Copy construction is allowed only for uninitialized objects");
}



FixedSizeAllocator& FixedSizeAllocator::operator=(const FixedSizeAllocator& iOther)
{
	//if(this != &iOther) //It's not a good idea... (item 38 sutter, except. c++)
	//{
		FixedSizeAllocator copy(iOther);
		copy.Swap(*this);
	//}
	return *this;
}



void FixedSizeAllocator::Initialize(const size_t iBlockSize, const size_t iPageSize)
{
	assert(mChunks.empty());
	assert(iBlockSize > 0);

	mBlockSize = iBlockSize;

	size_t numBlocks = iPageSize / mBlockSize;

	if(numBlocks > Chunk::MAX_NUM_BLOCKS)
		numBlocks = Chunk::MAX_NUM_BLOCKS;

	assert(numBlocks > 0);

	mNumBlocksPerChunk = static_cast<Chunk::BlockCounter>(numBlocks);

	//assert(mNumBlocksPerChunk == numBlocks); // overflow check
}



void FixedSizeAllocator::Swap(FixedSizeAllocator& ioOther)
{
	mChunks.swap(ioOther.mChunks);
	std::swap(mBlockSize, ioOther.mBlockSize);
	std::swap(mNumBlocksPerChunk, ioOther.mNumBlocksPerChunk);
	std::swap(mLastAllocationChunk, ioOther.mLastAllocationChunk);
	std::swap(mLastDeallocationChunk, ioOther.mLastDeallocationChunk);
	std::swap(mOnlyOneEmptyChunk, ioOther.mOnlyOneEmptyChunk);
}



Chunk* FixedSizeAllocator::SearchChunk(void* iPtr) const
{
	assert(!mChunks.empty());
	assert(mLastDeallocationChunk);

	const size_t chunkLength = mNumBlocksPerChunk * mBlockSize;

	if(mLastDeallocationChunk->HasBlock(iPtr, chunkLength))
	{
		return mLastDeallocationChunk;
	}

	Chunk* prev = mLastDeallocationChunk - 1;
	Chunk* next = mLastDeallocationChunk + 1;
	const Chunk* prevBound = &mChunks.front() - 1;
	const Chunk* nextBound = &mChunks.back() + 1;

	// Special case: mLastDeallocationChunk is the first in the array
	if(prev == prevBound)
		prev = nullptr;
	// Special case: mLastDeallocationChunk is the last in the array
	if(next == nextBound)
		next = nullptr;

	while(prev || next)
	{
		if(prev)
		{
			if(prev->HasBlock(iPtr, chunkLength))
			{
				return prev;
			}
			if(--prev == prevBound) 
			{
				prev = nullptr;
			}
		}
		
		if(next)
		{
			if(next->HasBlock(iPtr, chunkLength))
			{
				return next;
			}
			if(++next == nextBound)
			{
				next = nullptr;
			}
		}
//#ifdef _DEBUG
//	assert((prev != nullptr || next != nullptr) && "Do you attempt to deallocate an already allocated block?");
//#endif
	}
	return nullptr;
}



void* FixedSizeAllocator::Allocate(void)
{
	assert(0 != mBlockSize && "Object must be initialized!");
	assert(nullptr == mOnlyOneEmptyChunk || mOnlyOneEmptyChunk->HasAvailableBlocks(mNumBlocksPerChunk));

	if(nullptr == mLastAllocationChunk || mLastAllocationChunk->IsFull())
	{
		if( nullptr != mOnlyOneEmptyChunk)		// chunk available at zero cost!
		{
			mLastAllocationChunk = mOnlyOneEmptyChunk;
			mOnlyOneEmptyChunk = nullptr;
		}
		else
		{
			// Try to find an available chunk
			for(ChunksIter chunksIt = mChunks.begin(); ; ++chunksIt)
			{
				if(chunksIt == mChunks.end())
				{
					mChunks.reserve(mChunks.size()+1);
					Chunk newChunk;
					newChunk.Init(mBlockSize, mNumBlocksPerChunk);
					mChunks.push_back(newChunk);
					mLastAllocationChunk = &mChunks.back();
					mLastDeallocationChunk = &mChunks.back();
					break;
				}
				if(!chunksIt->IsFull())
				{
					// Found a chunk
					mLastAllocationChunk = &*chunksIt;
					break;
				}
			}
		}
	} 
	else if(mLastAllocationChunk == mOnlyOneEmptyChunk)
	{
		mOnlyOneEmptyChunk = nullptr;
	}
	assert(mLastAllocationChunk != 0);
	assert(!mLastAllocationChunk->IsFull());

	return mLastAllocationChunk->Allocate(mBlockSize);
}



void FixedSizeAllocator::Deallocate(void* iPtr)
{
	assert(0 != mBlockSize && "Object must be initialized!");
	assert(!mChunks.empty());
	assert(mLastDeallocationChunk >= &mChunks.front());
	assert(mLastDeallocationChunk <= &mChunks.back());
	assert(mLastAllocationChunk >= &mChunks.front());
	assert(mLastAllocationChunk <= &mChunks.back());
	
	Chunk* chunk  = SearchChunk(iPtr);

	Deallocate(iPtr, chunk);
}

void FixedSizeAllocator::Deallocate(void* iPtr, Chunk* iChunk)
{
	assert(0 != mBlockSize && "Object must be initialized!");
	assert(!mChunks.empty());
	assert(mLastDeallocationChunk >= &mChunks.front());
	assert(mLastDeallocationChunk <= &mChunks.back());
	assert(mLastAllocationChunk >= &mChunks.front());
	assert(mLastAllocationChunk <= &mChunks.back());

	mLastDeallocationChunk = iChunk;

	mLastDeallocationChunk->Deallocate(iPtr, mBlockSize);

	if(mLastDeallocationChunk->HasAvailableBlocks(mNumBlocksPerChunk))
	{
		assert(mLastDeallocationChunk != mOnlyOneEmptyChunk);

		if(nullptr != mOnlyOneEmptyChunk)
		{
			assert(mOnlyOneEmptyChunk->HasAvailableBlocks(mNumBlocksPerChunk));
			Chunk* lastChunk = &mChunks.back();

			if(lastChunk == mLastDeallocationChunk)
			{
				mLastDeallocationChunk = mOnlyOneEmptyChunk;
			}
			else
			{
				if(lastChunk != mOnlyOneEmptyChunk)
					std::swap(*lastChunk, *mOnlyOneEmptyChunk);

				mOnlyOneEmptyChunk = mLastDeallocationChunk;
			}

			assert(lastChunk->HasAvailableBlocks(mNumBlocksPerChunk));

			if((mLastAllocationChunk == lastChunk) || mLastAllocationChunk->IsFull())
				mLastAllocationChunk = mLastDeallocationChunk;

			lastChunk->Release();
			mChunks.pop_back();
		}
		else
		{
			if(mLastAllocationChunk->IsFull())
				mLastAllocationChunk = mLastDeallocationChunk;

			mOnlyOneEmptyChunk = mLastDeallocationChunk;
		}
	}

	assert(nullptr == mOnlyOneEmptyChunk || mOnlyOneEmptyChunk->HasAvailableBlocks(mNumBlocksPerChunk));
}

}